The flow of data in a network is accomplished by transmitting data from one network node to another node until the data arrives at the destination node. Various data protocols are used for transmitting data in the network, including TCP/IP HTTP and UDP. The protocol selected for a data transfer is based on the type of network, the network topology, the data type and other factors.
Two different protocol classes are available for transmitting data through a network: unicast routing protocols and multicast routing protocols. Unicast routing protocols transmit data from a single source node to a single destination node, typically through several intermediate nodes. Although unicast protocols, such as TCP (transmission control protocol), can be used for multicasting, they are not efficient when applied to multicasting as the data is sent multiple times from the source node to each destination node in the multicast group.
Multicast routing protocols transmit data from one or more source nodes to multiple destination nodes, and are designed to be more efficient when sending data to a large number of nodes. The multiple destination nodes are defined as members of a multicast group such that each member of the group receives data addressed to the group. In multipoint-to-multipoint multicast, each receiving node in the group receives data from every sender. If the multicast group is limited to a single sender, this is referred to as point-to-multipoint multicast. Exemplary multicast groups can include the group of all nodes receiving a software update generated at the source node or an update to a node address list that is directed to a network device, such as a switch. Multi-participant videoconferences, distance learning (where a teacher communicates with geographically dispersed students) and multiple emails to a news group are also multicast data transmittals. In one exemplary multicast routing protocol, the sending node transmits data to each multicast group member through a single transmission to a multicast group address. An underlying multicast delivery mechanism delivers the data to all of the destination receivers who have registered to be a part of the multicast group. Known techniques such as multicast data flooding and reverse-path forwarding provide the mechanism by which the data is received by all routers in the network that lie on a path to a receiving node in the multicast group.
In one conventional router implementation, each network router stores a linear list of multicast group members (indexed according to the destination address or destination identifier (DID) of the group members) for those multicast groups in which a destination node connected to the router is a member. In certain applications, the router stores multicast group lists for all possible multicast sessions that might occur on the network, regardless of whether the a particular link from the router is actually participating in a multicast session.
The contents of each destination address entry in the multicast linear list include various nodal and protocol attributes of the destination address, i.e., data transmission parameters. Generally, the contents describe where (over which output port) and when (with what priority) to send the packet to the destination address and the nature of any transformations required in the packet header to ensure the packet reaches the destination address. For example, an entry can include a queue identifier indicating the router output port through which the data must be sent to reach the destination address. Another item in the entry identifies any packet header transformations that are required to satisfy the requirements of the communications medium and the network protocol of the destination address (which may be different than medium and protocol of the source node). A list entry can further include a descriptor of the shortest path from the router to the destination node. At a minimum, information is required for each entry to indicate which headers to prepend to the packet for transmission on each of the outgoing medium. The linear list does not include a link at each entry; rather the entries are arranged in sequence. The last list entry includes an indicator asserting that the end of the list has been reached.
For some applications, namely emulation of broadcast in a virtual local area network environment, a multicast group list is stored in multiple versions, where each stored list includes all members of the group, minus one. Since there is one omitted member from each list, the number of multiple lists for a group is equal to the number of entries in the list. Significant storage capacity is required at each router to store these multiple versions for only a single multicast group.
When a multicast packet arrives at a network router, the sending node and the intended multicast group are determined from the received packet. This information is then used to select the appropriate group list where the source node is the omitted node from the list. Thus the packet is transmitted to the group, but since the source node is not included within the group list, the packet is not transmitted back to the source.
In certain embodiments, the members of the group may be local area networks, each comprising a plurality of nodes, rather than individual network nodes. The source node, which is thus a network, transmits the packet to all nodes within its network and requests transmittal of the packet to a multicast group. In this situation, it is particularly advantageous to prohibit transmittal of the packet back to the source node, since the packet would then be resent to each node of the source network, unnecessarily consuming significant bandwidth within the source network.
Rather than omitting one network node from each group list, according to another multicast technique, each linear list begins with a different member of the group. See FIG. 1 where an “A” multicast group includes seven members, with their addresses indicated by the characters A1 through A7. Each “A” group list begins with a different group member. According to this embodiment, the multicast packet data received at the router includes certain header information from which a an optional skip first flag identifier is derived. The incoming packet is processed through a classification engine, for determining the incoming port and the destination identification from the packet header. Also, the header includes information from which the value (i.e., set or not set) of the skip first flag is determinable. For example, the address in the packet header can specify a multicast packet and the classification engine can be programmed to recognize this address and generate the correct destination addresses and the skip first flag value based thereon.
The router classifying engine then reads the address and flag information and selects the correct multicast group list by matching the source address with the first entry in a group list. If the skip first flag is set, the data is not sent to the first address in the group.
If there are N members in a multicast group, each serving as a source for a multicast packet, and the packet must be sent to all other members of the group, then N lists are required. But each list has (N−1) entries because the packet is not sent back to the source node. Thus (N)(N−1)memory locations are required to store all group lists, where each list includes all members of the group except one. Therefore, the storage requirements at each router can be considerable if N is relatively large, as it would typically be.
In another embodiment where the data is transmitted to the receiving nodes of the multicast group in a specific order, then additional group lists are required, with each group list setting forth a different order for the receiving nodes. See FIG. 2 where eight different ordered lists are illustrated, each having destination identifier “A1” at the top of the list. There are a total of 720 different ordered lists with “A1” as the first entry. Similarly, there 720 lists with “A2” as the first entry. Thus for a relatively small group list of seven members, there are 5040 different lists to be maintained. Since many such lists are maintained for many multicast groups at each router, the memory storage requirements can be extreme.